Delta 压缩

译：https://hashnode.com/post/delta-compression-a-practical-guide-to-diff-algorithms-and-delta-file-formats-ckcbslwu9001281s1acm2fhz2

Diff 算法（差分算法）

目的和用途
差分算法的输出称为 patch 或 delta。delta 格式可能是人类可读文本格式，也可能是机器可读二进制格式。人可读格式通常用于跟踪和调节对源代码等人可读文本的修改。二进制格式通常经过空间优化，用于节省带宽。与传输所有新数据相比，它只传输对接收方已有数据旧版本的一系列更改。这种格式的正式术语是 delta 编码。

二进制 vs. 文本？
差分算法可以处理任何输入，只要输入可以被简单地视为一串字节。这个字符串可以是英文字母，也可以是不透明的二进制数据。

diff/merge 工具产生的文本 diff 输出有基于行、基于字和基于字符的分类。基于行/字/字符并不是差分算法本身的特征；相反，它是在输入到实际差分算法之前对输入进行的优化。由于新行和空格在人类可读文本中具有分隔符的意义，因此差分工具可以根据文本中行或词的哈希值分割字符串。这种哈希字符串比原始文本短得多，因此可以节省时间，但代价是降低了差异的粒度。此外，在某些情况下，基于行的粒度甚至会提高差异的可读性。

如果已知输入是不透明的二进制数据，则既没有有意义的分隔符，也没有人类可读的差值可显示，因此无法应用这种优化。因此，能够在输入之前优化人类可读数据的算法很容易被误认为完全无法处理二进制数据。但事实仍然是：除了预处理优化，二进制数据和人类可读数据都可以被视为字节字符串输入，并很容易处理。

三代 diff 差分算法

字符串到字符串的更正或插入/删除

第一代 diff 算法解决了字符串到字符串的校正问题，出现于上世纪六七十年代。两个输入中的每一个都被解释为由某个字母表中的字符组成的字符串。输出是字符编辑序列，最常见的是插入/删除操作，可应用于其中一个输入，将其转换为另一个输入。因此，这类算法特别适合在人类可读的输入上生成人类可读的差异，例如，随着时间的推移进行实际编辑而产生的同一文本/源代码的不同版本。理论上，通常在实践中，完成任务的最小长度编辑操作序列不止一个。可以使用各种启发式方法来选择最接近实际人工编辑的编辑序列。

Wagner-Fischer 算法为这一代差异算法奠定了基础。Myers Algorithm 是这一代算法的最新改进和事实上的标准，目前被包括 GNU diff 工具在内的多种 diff 工具所采用。这一代算法通常会找到最长公共子序列或最小编辑距离（通常是 Levenshtein 距离），并利用它们生成将一个输入转化为另一个输入所需的编辑序列。

块移动或复制/插入

单纯的块移动
与上一代相比，下一代差异算法进行了看似微小的优化。字符编辑升级为字符块编辑。也就是说，差异不再用对单个字符的操作来表示，而是用对字符块的操作来表示。这种操作通常是复制和插入，即在两个输入中都出现的数据块被记录在 delta 中，从一个输入复制到另一个输入。其中一个输入中独有的数据块被记录为插入。这种方法最早由 Walter Tichy 提出。

基于压缩的区块移动
从复制数据块的角度来考虑差异生成，并注意同一数据块是否重复多次，这就为使用压缩算法生成 diff 和 delta 文件打开了大门。
压缩算法就是这样做的：找出尽可能大的重复数据块，并将每个连续出现的数据块替换为第一次出现的数据块。从不重复的数据块则直接复制到输出端。压缩算法本质上是数据块移动算法。

如果对差分算法的两个输入数据都进行压缩算法的数据块移动分析，就能很容易地找出两个输入数据的共同部分。它还会指出哪些数据块是唯一的，即在两个输入中都是不同的。有了这些数据后，就可以直接提出一个数据块复制/删除操作序列，将其中一个输入转换为另一个输入。

使用压缩算法的主要好处是大大减少了 delta 的大小。一个数据块在 delta 中出现的次数绝不会超过一次。它可能会被多次引用，但数据块的实际数据只会在 delta 中出现一次。这是与前面几种方法的主要区别。还应该提到的是，delta 大小的减少是以降低人类可读性为代价的。
xDelta、zDelta、Bentley/McIlroy 是这一代差分算法广泛使用的事实上的标准实现。

最新升级

这是最新一代的差分算法。它的大多数成员只存在于研究论文中，还没有任何商业实现。它们在很大程度上基于分块移动方法，但在实现上进行了大量优化，与上一代相比，速度据称提高了两位数。

这些优化主要侧重于在两个输入中高效地找到匹配的数据块。为实现这一目的，使用了各种增量散列或类似压缩的技术（如后缀树）。
edelta、ddelta、bsdiff 可以归类到这一代的差异算法中。

目前使用的 Delta 生成算法

截至 2019 年 6 月可用的、专注于高效生成 delta/patch 文件的工具和库。

Myers Algorithm

Myers 算法属于字符串校正系列，广泛应用于各种工具，这些工具经过微调，可以从人类可读的输入中生成人类可读的 delta/patch 文件。Git Diff 和 GNU Diff 等工具就使用了这种算法。

算法最初的时间和空间复杂度为 $O(ND)$，其中 N 是两个输入的长度之和，D 是将一个输入转换为另一个输入的最小编辑脚本的大小。当差异数较少时，如编辑相同的代码/文本文件，该算法速度很快。对迈尔斯算法进行了各种优化后，时间和空间分别提高到 $O(NlgN + D^2)$ 和 $O(N)$。

Bentley-McIlroy

Bentley-McIlroy 算法属于块移动系列，主要用于生成最佳大小的 delta/patch 文件。该算法在不同的平台和语言上有不同的实现方式，因此可以被认为是 delta 大小重要的情况下的一种事实上的标准。谷歌的 Open VCDiff 是 Bentley-McIlroy 最突出的应用之一，它能够生成 VCDiff 格式的 delta/patch 文件。

算法的时间复杂度为 $O(sqrt(N)\times N)$，尽管作者声称在平均情况下是线性复杂度。内存复杂度为线性。

XDelta

XDelta 算法属于分块移动算法系列，主要关注 delta 生成的速度。为了提高速度，该算法牺牲了 delta 的大小。xdelta delta 生成工具是 XDelta 的最主要用途，也能生成 VCDiff 格式的 delta/patch。

XDelta 算法具有线性时间和空间复杂性。

BSDiff

BSDiff 算法属于块移动系列，主要用于实现最小的 delta/patch 大小。它还专门针对可执行文件进行了优化。bsdiff 工具是 BSDiff 算法最主要的应用。bsdiff 工具使用自己定制的 delta/patch 文件格式。

BSDiff 的时间复杂度为 $O((n+m)log(n))$，其中 n 和 m 是两个输入的大小。其内存复杂度为 $\max(17n,9n+m)+O(1)$。

Delta 文件格式

就 delta/patch 文件而言，问题更多在于缺乏标准。许多差异工具和库都以各自的自定义格式生成 delta/patch 文件，因此只有补丁的制作者才能应用它。
在这种情况下，历史上出现了两种主要的 delta/patch 格式标准化尝试。

Unix .patch

这是由 GNU diff 工具生成的 delta/patch 格式系列，旨在提高人类的可读性。GNU diff 工具存在已久，这些补丁格式被各种文本处理工具和源码控制系统广泛接受/使用，无论是否经过修改。

VCDiff

VCDiff 是在创建数据无关、算法无关的 delta/patch 格式方面最突出的尝试，旨在实现应用的紧凑性和速度。VCDiff 因谷歌的 SDCH（Shared Dictionary Compression for HTTP，HTTP 共享字典压缩）而获得广泛采用。如今，多种差异算法实现都能生成 VCDiff 格式的 delta/patch 文件。VCDiff delta 应用程序库的成熟度各不相同，适用于大多数流行语言和平台。

参考

• https://github.com/jmacd/xdelta
• https://github.com/google/open-vcdiff